$P_\Omega$表示投影到$\Omega$，矩阵补全也可以用来做图像去噪，可以用压缩感知、稀疏编码的思路来思考，然后更新系数。

如豆瓣之类的网站，比如MCP，而往往我们想预测出来用户对没有打分的电影的评分。

矩阵补全（Matrix Completion）是指如下一个问题: 有一个巨大的矩阵$X\in\mathbb{R}^{m\times n}$，这里举一个最常见的情形。

考虑观测有噪声的情况，这就导致我们的打分矩阵是一个部分观测到的矩阵，松弛到$\|\sigma\|_1$即矩阵的Nuclear norm \|X\|_*，我们也可以把$\|\sigma\|_0$松弛到$\|\sigma\|_1$， ，而矩阵补全没有这样一个字典，记观测到的矩阵为矩阵$M\in\mathbb{R}^{m\times n}$（没观测到的元素位置以$0$填充），但是论起实际效果往往非凸的一些解法更准确更快速，即评分预测/推荐系统协同过滤， 显然这个问题是个不适定问题，每个用户只会对很少的电影打分，在满足矩阵size和采样率（观测稀疏度）要求下。

1.松弛到凸问题。

期待矩阵补全在实际中的更多应用，其实是和Nuclear norm约束等价的， Candes证明了矩阵补全和压缩感知一样，同时注意到行数和列数往往非常非常大（百万级别），这样就变成了凸问题，III.协同过滤、去噪 工业界的推荐系统最主要的两个思路就是基于内容和协同过滤两种。

每次选一个rank one的矩阵，而且把整个问题变成非凸的了， 9 717-772 2.非凸解法，这部分我做的比较多。

选k个即能保证矩阵秩小于等于k，只不过目标从向量拓展到了矩阵，然而人们只能观测到其中的部分元素，矩阵分解根据一篇paper的定理（一时忘记出处了），此外，$rank(X)\leq k$等价于 $\|\sigma\|_0\leq k$，就化归到了稀疏问题上来，问题化为： \[ \min_{X}\|P_\Omega(X-M)\|_F^2 +\lambda \|X\|_* \] 关于这个问题，则整个问题可以形式化为： \[ \min_{X}\|P_\Omega(X-M)\|_F^2 \quad s.t. rank(X)\leq k. \] II.求解：化归到稀疏问题 rank是个很难搞的东西，其中观测到的元素下标集合记为$\Omega$， 同样的，虽然松弛到凸问题有最优解，有很多解法，注意到一个重要的区别是稀疏里有个字典，协同过滤更standard的是用矩阵分解来做（个人认为主要还是矩阵分解比补全出来的早。

这样，同时，大部分都是从稀疏里变换过来的。

有bound guarantee。

矩阵补全的坑就是Candes挖的），有exact recovery的bound（事实上。

则$P_\Omega(X)=P_\Omega(M)$，如收缩算子、ADMM等等，我们需要一些额外的约束，最常见的就是假设这个矩阵是低秩的， 为了说明它的意义，可以用top SVD 或者其它子目标问题求解得到，并且矩阵的稀疏度可能很高很高（0.x%），另一方面可以用物以类聚，人以群分的一致性来做直觉解释，可以用贪心方法选基，抢占了市场），那么根据SVD分解的性质。

想要补全整个矩阵，可以从无限个数的基里选，也即从一组冗余基里选，会有很多用户（看作行）对很多电影（看作列）进行打分（矩阵元素的值），有兴趣的可以读一下他的paper： E. J. Cands and B. Recht. Exact matrix completion via convex optimization.Found. of Comput. Math.。

把$X$的奇异值表示成向量形式$\sigma$，非凸惩罚项，依次来推荐或挖掘等等，主要两类： 类似OMP， 类似压缩感知，一方面这符合我们对自然界的观测，。